package leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMax {

	public static void main(String[] args) {
		int[] nums = {4, 6, 3, 2, 7, 9, 8, 1, 2, 3, 5, 6, 1};
		SlidingWindowMax object = new SlidingWindowMax();
		int[] res = object.maxSlidingWindow(nums, 6);
		for (int i = 0; i < res.length; i++) {
			System.out.print(res[i] + " ");
		}
		System.out.println();
	}
	
	
	//求滑动窗口的最大值
	public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < k || k <= 0){
            return nums;
        }
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> queue = new LinkedList<Integer>();
        //由于要处理超界的情况，所以我们不直接将元素放至队列
        //我们放入下标
        for(int i = 0; i < k - 1; i++){
        	//如果元素大于队尾的元素，队尾出队，直到该元素小于队列队尾的元素
        	while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
        		queue.removeLast();
        	}
        	queue.addLast(i);
        }
        System.out.println(queue);
        for(int i = k - 1; i < nums.length; i++){
        	//还要注意滑动窗口超界的情况
        	if(!queue.isEmpty() && i - queue.peekFirst() >= k){
        		queue.removeFirst();
        	}
        	while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
        		queue.removeLast();
        	}
        	queue.addLast(i);
        	res[i - k + 1] = nums[queue.peekFirst()];
        	System.out.println(queue);
        }
        return res;
    }
}
